// 时间复杂度O(n^2)
// 空间复杂度O(1)

const { LinkedList } = require('../1. 链表基础/1. 建立线性链表')

function sectionSort(head) {
    let i = head
    // i为当前未排序链表的第一个链接点
    let min = i
    while (i && i.next) {
        min = i
        let j = i.next
        while (j) {
            if (j.val < min.val) {
                min = j
            }
            j = j.next
        }
        // 交换最小值与未排序链表中的第一个节点的值
        if (i !== min) {
            [i.val, min.val] = [min.val, i.val]
        }
        i = i.next
    }
    return head
}

const linkList = new LinkedList([2, 5, 1, 6, 3, 4])
sectionSort(linkList.head)
console.log(linkList);